package bstsetcode;

import java.util.Arrays;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/16 7:04
 */
public class MergeSortDebug {

    public static <E extends Comparable<E>>  void sorted(E[] data){
        int left = 0;
        int right = data.length-1;
        int depth = 0;
        mergeSorted(data,left,right,depth);
    }

    private static <E extends Comparable<E>> void mergeSorted(E[] data, int left, int right,int depth) {
        //生成字符串深度
        String depthString = generateDepthString(depth);
        //打印当前sort处理的数组区间信息
        System.out.print(depthString);
        System.out.println(String.format("mergesort arr[%d, %d]",left,right));



        if(left >= right) {
            return;
        }

        int mid = (left + right )/2;

        //对arr[l,mid]进行排序
        mergeSorted(data,left,mid,depth+1); //深度+1
        mergeSorted(data,mid+1,right,depth+1);

        System.out.print(depthString);
        System.out.println(String.format("merge data[%d,%d] and data[%d,%d]:",left,mid,mid+1,right));
        //合并
        merge(data,left,mid,right);
        //打印merge后的数组
        System.out.print(depthString);
        System.out.println(String.format("after mergesort data[%d,%d] :",left,right));

    }

    private static String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            res.append("--");
        }
        return res.toString();

    }

    private static <E extends Comparable<E>> void merge(E[] data, int left, int mid, int right) {
            E[] temp = Arrays.copyOfRange(data,left,right+1);

            int i = left,j=mid+1;

        for (int k = left; k <= right; k++) {
            //判断越界的情况
            if(i > mid){ //左边数组没有数据，直接赋值有边数组的值
                data[k] = temp[j-left];
                j++;
            }else if( j > right){
                data[k] = temp[i-left];
                i++;
            }else if(temp[i-left].compareTo(temp[j-left]) <= 0){
                data[k]=temp[i-left];
                i++;
            }else{
                data[k]=temp[j-left];
                j++;
            }
        }

    }

    public static void main(String[] args) {
        Integer []  arr = {1,9,4,3,6,5,7};
        MergeSortDebug.sorted(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }



    }

}
